Finding effectors in social networks
Theodoros Lappas
Evimaria Terzi
Dimitrios Gunopulos
Heikki Mannila
Assume a network (<i>V,E</i>) where a subset of the nodes in <i>V</i> are <i>active</i>. We consider the problem of selecting a set of <i>k</i> active nodes that best explain the observed activation state, under a given information-propagation model. We call these nodes <i>effectors</i>. We formally define the <i>k</i>-Effectors problem and study its complexity for different types of graphs. We show that for arbitrary graphs the problem is not only NP-hard to solve optimally, but also NP-hard to approximate. We also show that, for some special cases, the problem can be solved optimally in polynomial time using a dynamic-programming algorithm. To the best of our knowledge, this is the first work to consider the <i>k</i>-Effectors problem in networks. We experimentally evaluate our algorithms using the <b>DBLP</b> co-authorship graph, where we search for effectors of topics that appear in research papers.
